#coding=utf-8
def build_box(things : list , c : int) -> list:
    things = sorted(things)
    res = []
    while things:
        n = c
        temp = []
        for i in range(len(things))[::-1]:
            if things[i] <= n:
                temp.append(things[i])
                n -= things[i]
                things.pop(i)
        res.append(temp)
    return res


def greedy(k, t, job):
 # 计算每个工人理想的平均花费时间
 avgT = sum(job) / k
 beginIdx = 0
 ansT = 0
 # 如果 len(job) - beginIdx == k 或者 k == 1，则剩下的活一人一个
 while len(job) - beginIdx > k > 1:
     curT = job[beginIdx]
     beginIdx += 1
     for endIdx in range(beginIdx, len(job) - k + 1):
         # 选择与平均消耗时间最接近的组合
         if abs(curT - avgT) > abs(curT + job[endIdx] - avgT):
             curT += job[endIdx]
             beginIdx += 1
         else:
             break
     ansT = max(ansT, curT)
     k -= 1
 ansT = max(ansT, max(job[beginIdx:]))
 return ansT * t


from collections import deque,defaultdict

import heapq
class Graph():
    def __init__(self):
        self.adj = defaultdict(dict)
class PriorityQueue:
    def __init__(self):
        self.key = defaultdict(int)
        self.pqueue = []


def prim(graph:Graph,source:str)->dict:
    Q = PriorityQueue()
    mst = {}
    parent = {}
    for v in graph.adj:
        if v == source:
            Q.key[v] = 0
            heapq.heappush(Q.pqueue,(0,v))
        else:
            Q.key[v] = float('inf')
            heapq.heappush(Q.pqueue,(float('inf'),v))
    parent[source] = None
    while Q.pqueue:
        print(Q.pqueue)
        (v_key,v) = heapq.heappop(Q.pqueue)
        del Q.key[v]
        mst[v] = parent[v]
        for u in graph.adj[v]:
            if u in Q.key and u not in mst:
                if graph.adj[v][u] < Q.key[u]:
                    ind_key = Q.pqueue.index((Q.key[u],u))
                    Q.pqueue.pop(ind_key)
                    heapq.heappush(Q.pqueue,(graph.adj[v][u],u))
                    Q.key[u] = graph.adj[v][u]
                    parent[u] = v
    return parent



def Dijkstra(graph:Graph,source:str)->dict:
    priority_queue = []
    heapq.heappush(priority_queue,(0,source))
    visited = {}
    while priority_queue:
        print(priority_queue)
        (current_distance,current) = heapq.heappop(priority_queue)
        if current not in visited:
            visited[current] = current_distance
        if current not in graph.adj:
            continue
        for neighbour , distance in graph.adj[current].items():
            if neighbour in visited:
                continue
            new_distance = current_distance + distance
            heapq.heappush(priority_queue,(new_distance,neighbour))
    return visited



if __name__ == '__main__':


    #1
    # things = list(map(int,input("请输入物品重量，用空格分开： ").split()))
    # c = int(input("请输入箱子容量： "))
    # res = build_box(things,c)
    # print(f"最少需要{len(res)}个箱子，分别装入： ",end='')
    # print(*res)




    #2
    # k = int(input("请输入工人数量： "))
    # T = int(input("请输入工人完成任务的单位时间： "))
    # job = list(map(int, input("请输入任务完成的时间，用空格分开： ").split()))
    # print(f"最少需要{greedy(k,T,job)}个单位时间")

    #3
    graph = Graph()
    graph.adj = {'g': {'c': 7, 'h': 15, 'f': 10},
                 'a': {'b': 6,'f':8,'c':5,'e':14},
                 'c': {'a': 5, 'b': 12,'d':9,'g':7},
                 'b': {'a': 2,'c':12},
                 'e': {'a': 14, 'f': 3},
                 'd': {'c':9},
                 'h': {'g':15},
                 'f': {'a':8,'e':3,'g':10}}
    print(prim(graph, 'g'))

    #4
    # graph = Graph()
    # graph.adj = {'s':{'a':4,'c':8,'b':16},
    #              'a':{'c':3},
    #              'c':{'b':7,'e':1},
    #              'b':{'d':2},
    #              'e':{'b':5,'d':6},
    #              'd':{}}
    # print(Dijkstra(graph,'s'))
